## Un peu de contexte
C'était lundi. Nous étions en train de finir d'extraire une liste de noms propres pour améliorer l'[annotation](/articles/Le%20tronçonneur%20des%20Lilas.html) de l'[Encyclopédie](https://fr.wikisource.org/wiki/Encyclop%C3%A9die,_ou_Dictionnaire_raisonn%C3%A9_des_sciences,_des_arts_et_des_m%C3%A9tiers) (celle qui n'a pas besoin d'autre titre, celle qui a fixé les règles modernes du genre, celle de Diderot & d'Alembert).
Notre annotateur n'est pas mauvais, il a été développé spécialement pour traiter du français ancien et supporte à merveille les «étoit» et autres «enfans». Par contre, il est super mauvais sur les noms propres. Il comprend qu'il s'agit de noms, mais il n'ose pas affirmer qu'ils sont propres, même en voyant leur majuscule initiale. Ce n'est pas un signe de rebellion, probablement n'y en avait-il pas assez dans le corpus annoté manuellement qui a permis de l'entraîner; toujours est-il que pour lui «Pline», «Garonne» et «Théophrone» sont des noms communs. «Sozomène» ? Un nom commun aussi.
En terme de recherche d'information, on dit qu'il a un faible [taux de rappel](https://fr.wikipedia.org/wiki/Pr%C3%A9cision_et_rappel). Ça veut dire qu'il ignore plein de réponses qui étaient en fait valides (il y a beaucoup de faux négatifs). Par contre sa précision est assez bonne, il n'inclut pas trop de faux positifs dans les réponses.
Bref, nous étions en train d'aboutir petit à petit à cette liste de noms dont nous étions à peu près sûrs qu'ils étaient, toujours, systématiquement des noms propres, et que nous pouvions rectifier leur étiquette morpho-syntaxique à chaque occurrence dans le corpus. Si tu vois «Pline» quelque part, c'est même pas la peine de t'intéresser à des règles compliquées de syntaxe ou d'essayer de faire des statistiques sur l'annotation morpho-syntaxique des autres termes proches dans la phrase, **c'est** un nom propre, point. C'est à ce moment que le chef a prononcé cette phrase funeste : «bon, bin tu finis d'affiner la liste et ce serait bien si tu pouvais ensuite relancer un import du corpus avec les étiquettes de tous ces noms propres corrigés». Je dis «funeste», car il était 17h30.
À sa décharge, il ne pouvait pas savoir ce que sa phrase impliquait, le pauvre. C'est moi qui lui avait dit : «oui, à partir d'une liste, c'est hyper simple de remplacer la `POS`[^POS] de toutes les occurrences d'un ensemble de mot». C'est vrai, il s'agit seulement de recherche et de remplacement, deux opérations pratiquement pour lesquelles les ordinateurs ont été inventés. J'ai dit simple, mais il a compris rapide. Or, ça, comme nous l'allons voir, c'est une autre paire de manches.
## Comment on fait ?
Bon déjà, le corpus. Il s'agit des articles de l'Encyclopédie, il y en a 74198 chacun dans un fichier séparé. Cela représente 1.5G de données (c'est bien du format texte, mais il y a pas mal d'enrobage autour de chaque article, les header XML-TEI, beaucoup d'information redondante, le texte quasi-brut de l'Encyclopédie en un fichier par tome et où donc cet enrobage n'apparaît que 17 fois et pas 74198 fois ne pèse que 170M — pas mal, déjà, pour du texte). Pour simplement lister tout le contenu du répertoire et ignorer le résultat (jeter les lignes au lieu de les afficher), il me faut déjà 1.7s. La liste détaillée avec les métadonnées de chaque fichier, permissions etc., un par ligne, pèse déjà 5M.
Intuitivement, ce qu'on voudrait faire est simple : on voudrait itérer sur ces fichiers, ce qui se fait facilement avec la commande `find`, et pour chacun, remplacer la `POS` sur toutes les lignes où le mot est dans la liste donnée. Cette deuxième partie a l'air d'une tâche naturelle pour la commande `sed`. Problème, `sed` ne fait pas dans les listes de fichier en entrée ou, alors, ne les combine que très mal avec une vraie expression de recherche / remplacement. Cette appartenance à une liste, moralement, c'est une disjonction en terme d'expression régulière. Je veux qu'à cet endroit de la ligne apparaisse ou le premier élement de mon ensemble, ou le deuxième, ou le troisième… Mais la liste de noms propres à laquelle nous avons abouti comporte quand même environ 19000 éléments. Hmmm, je pense que `sed` va moyennement aimer la génération d'une disjonction gigantesque en concaténant tout ce beau monde, séparé par des `|`. En vrai, ce serait plutôt `grep` qui dispose d'une super fonctionnalité de recherche en prenant une liste de fichier en entrée. sauf que `grep`, lui, ne s'occupe bien sûr pas du remplacement.
Et c'est là qu'on voit les soucis s'accumuler : oui, ça doit bien se faire mais… mais finalement on va se retrouver à lire le fichier ligne par ligne, à faire un `grep` sur la ligne et, dans le cas où l'on trouve une correspondance, sortir une ligne éditée plutôt que de la recopier telle quelle sur la sortie. Quelque chose comme
```bash
find CORPUS/ -type f -name '*.xml' | while read ARTICLE
do
while read LINE
do
FIXED_ARTICLE="${ARTICLE/CORPUS/CORPUS.fixed}"
if echo "${LINE}" | sed 's|>\(.*\)</w>$|\1|' | grep -q -f PROPER_NOUNS_LEXICON -x
then
echo "${LINE}" | sed 's|pos="[^"]\+"|pos="Np"|'
else
echo "${LINE}"
fi
done < "${ARTICLE}" > "${FIXED_ARTICLE}"
done
```
Je vous raconte pas le travail. L'inefficacité absolue. Itérer ligne par ligne, lancer au moins une instance de `sed` et de `grep` à **chaque** ligne de **chaque** fichier de l'Encyclopédie. Instance de `grep` qui devrait, à chaque fois, charger ce lexique de presque 20000 mots.
Conceptuellement, ça reste simple, hein, je n'ai pas menti. Sauf que là on parle d'un calcul de plusieurs heures minimum pour la machine. Là j'ai commencé à me dire que j'allais m'acheter un duvet en urgence et faire une pyjama party au labo. Moyen, quand même : /
Et c'est là que j'ai eu une idée : c'est mal de réinventer des outils qui existent déjà, mais je pourrais très bien faire ces opérations de filtrage par ligne et de remplacement dans un langage que je connais bien, un langage compilé, qui donne en sortie du code machine efficace et qui me permettrait, au niveau de l'architecture, de factoriser les opérations coûteuses comme l'import du lexique de noms propres. Tiens, si je l'écrivais en Haskell ? : )
On m'a souvent demandé à quel point il était faisable et pratique d'utiliser ce langage pour faire de *vraies* choses, utiles, alors qu'il s'embête avec des notions de pureté, et qu'il empêche de faire des choses simples comme modifier la valeur des variables. Je pense que ce cas d'usage est un excellent exemple de ce qu'Haskell permet d'accomplir.
## C'est parti !
Alors vu que j'écrivais ce qui moralement était un script, un outil simple pour résoudre un problème précis et qui n'était pas destiné à devenir une composante permanente d'un système plus complexe, utilisé par d'autres gens, je me suis permis d'écrire assez simplement, sans une description très poussée de la syntaxe et de l'utilisation.
Déjà, je voulais m'occuper le moins possible des opérations fastidieuses de parcours du répertoire, qui sont toujours sources de problèmes, il faut faire attention à exclure les dossiers `.` et `..`, en plus dans mon cas j'ai d'autres fichiers du corpus à ignorer — principalement des métadonnées — et donc je voulais laisser `find` faire son travail, qu'il fait très bien. J'ai donc choisi d'itérer sur l'entrée standard, en attendant un fichier par ligne, le format que délivre `find`.
```haskell
module Main where
import System.Environment (getArgs)
import System.Exit (die)
import System.FilePath.Posix (replaceDirectory)
sed_i :: FilePath -> IO ()
sed_i file = do
putStrLn destFile
where
destFile = replaceDirectory file "CORPUS.fixed"
main :: IO ()
main = do
args <- getArgs
case args of
[lexiconFile] -> do
files <- lines <$> getContents
mapM_ sed_i files
_ -> die "Syntax: setPOS PN_LEXICON (filters files which paths are read on stdin)"
```
Première étape, un brouillon. Je jette juste l'ébauche de la structure du programme final en vérifiant la présence d'un unique argument qui sera le nom du lexique des mots dont on veut aller modifier la `POS`. Ayant encore en tête le script précédent, je considère que la fonction qui va agir sur chaque fichier est à rapprocher du `sed -i` que j'aurais écrit en bash. Mais en fait, elle porte mal son nom : Haskell a plutôt une tendance générale à ne pas modifier les objets existants mais à en renvoyer de nouveaux. Il existe sans doute une fonction pour modifier le contenu d'un fichier en place mais il me paraissait nettement plus simple d'aller créer un nouveau fichier avec le contenu édité en utilisant juste `writeFile`. J'anticipe sur la prochaine étape, mais, voulant m'assurer que tout marchait et que je n'allais pas écraser les précieuses données de mon corpus, je me suis d'abord arrêtée à cette première base qui compile et pour la lancer et vérifier que je récupérais correctement les noms en entrée et que le nom du fichier que j'allais écrire était exact.
Le niveau de stress était quand même assez élevé et je voulais avancer par petites étapes stables et maîtrisables plutôt que d'écrire d'un coup tout le logiciel et pleurer à la fin parce que je ne comprenais pas ce qui ne marchait pas alors que je manquais déjà cruellement de temps. Il m'a fallu environ 15 mn pour cette première partie.
## T+15 mn
Pour la deuxième étape, j'ai voulu détailler ce qui se ferait dans mon `sed -i` (qui n'en est pas un, donc, c.f. ci-dessus). Je ne vais donc rien modifier et me contenter de recopier chaque ligne telle quelle, mais le faire en considérant les lignes individuellement comme ce serait le cas à la fin. On est quasiment au niveau d'un petit tutoriel Haskell pour débutant qui montre l'emploi de `readFile`, `writeFile`, et les opérations de base sur les listes.
```haskell
module Main where
import Lexicon (Lexicon, load)
import System.Environment (getArgs)
import System.Exit (die)
import System.FilePath.Posix (replaceDirectory)
sed_i :: Lexicon -> FilePath -> IO ()
sed_i lexicon file = do
input <- lines <$> readFile file
writeFile destFile $ unlines input
where
destFile = replaceDirectory file "CORPUS.fixed"
main :: IO ()
main = do
args <- getArgs
case args of
[lexiconFile] -> do
lexicon <- load lexiconFile
files <- lines <$> getContents
mapM_ (sed_i lexicon) files
_ -> die "Syntax: setPOS NP_LEXICON (filters files according to names read on stdin)"
```
De plus, puisque j'ai bien dégagé l'identification de l'argument pour le lexique, on va commencer à définir ce que sera le lexique. J'ai écrit un petit module à part en pensant que ça serait compliqué mais retrospectivement, ça aurait bien pu aller dans le même module.
```haskell
module Lexicon (
Lexicon
, load
) where
import Data.Set (Set, fromList)
type Lexicon = Set String
load :: FilePath -> IO Lexicon
load = fmap (fromList . lines) . readFile
```
C'est très simple grâce à ce dans quoi Haskell brille : de la composition de fonctions, de l'abstraction haut-niveau où on n'a pas besoin de manipuler des valeurs. C'est quoi charger un fichier ? Bin tu commences par le lire, et à l'intérieur de la monade `IO` dans laquelle aura lieu sa lecture, tu fais une liste de ses lignes et tu crées un ensemble à partir de cette liste.
Bon, bien sûr en vrai ça n'a pas été aussi direct en partant du fichier vierge, surtout avec le stress de la montre. Mais en 5 mn, c'était réglé : j'avais bien réécrit un `cp` compliqué en Haskell, qui répliquait mon corpus à une vitesse folle.
## T+20 mn
Rendue là, j'ai commencé à atteindre une sensation d'excitation, parce que je n'avais rien fait de compliqué, mais je me suis rendue compte que j'étais à deux doigts d'avoir ce que je voulais. Encore un dernier coup de collier pour faire le remplacement à l'intérieur d'une ligne identifiée.
Je ne connais pas vraiment de modules d'expressions régulières en Haskell donc je me suis dit que j'allais faire l'impasse dessus plutôt que de perdre 1h à me familiariser avec les subtilités qui parsèmeraient à n'en pas douter un module capable de gérer ce genre de bête avec un système de type cohérent. À la place, je me suis dit que j'allais juste couper des chaînes. J'ai commencé par jouer avec la fonction `strSplit` du module Data.Strings :
```haskell
import Data.Set (member)
import Data.Strings (strSplit)
setLabelPN :: Lexicon -> String -> String
setLabelPN lexicon line =
let (a, rest) = strSplit "\">" line in
let (word, b) = strSplit "</w>" rest in
if word `member` lexicon
then ???
```
Et puis, à ce point-là, en plus de craindre légèrement mon code qui allait devenir un peu sale avec toutes ces opérations de `strSplit` répétitives qui, renvoyant toutes des nouvelles chaînes, allaient me demander de gérer manuellement une notion d'«état» en trouvant un nom de variable pour chaque état. Déjà mon `rest`, je sais pas vous mais moi je le trouve douteux. Je l'ai écrit parce que j'étais pressée mais je n'irais pas en place publique le défendre. Surtout que j'étais partie pour refaire la même chose une deuxième fois, mais cette fois non pas pour isoler un mot à chercher dans le lexique mais pour remplacer cette partie. J'ai donc écrit une fonction bien propre qui couperait en trois parties une chaîne passée en entrée selon deux motifs de délimitation.
```haskell
between :: (String, String) -> String -> (String, String, String)
between (opening, closing) haystack =
let (begining, rest) = strSplit opening haystack in
let (word, end) = strSplit closing rest in
(begining ++ opening, word, closing ++ end)
```
Forte de cette fonction, la précédente devient bien plus simple à écrire et à compléter :
```haskell
setLabelPN :: Lexicon -> String -> String
setLabelPN lexicon line =
let (_, word, _) = between ("\">", "</w>") line in
if word `member` lexicon
then
let (begining, _, ending) = between ("pos=\"", "\" ") line in
begining ++ "Np" ++ ending
else line
```
Et voilà, c'était tout. Plus qu'à appliquer ce filtre sur toutes les lignes plutôt que de les laisser inchangées comme dans la version précédente
```diff
- writeFile destFile $ unlines input
+ writeFile destFile $ unlines (setLabelPN lexicon <$> input)
```
Voici la version finale.
```haskell
module Main where
import Data.Set (member)
import Data.Strings (strSplit)
import Lexicon (Lexicon, load)
import System.Environment (getArgs)
import System.Exit (die)
import System.FilePath.Posix (replaceDirectory)
between :: (String, String) -> String -> (String, String, String)
between (opening, closing) haystack =
let (begining, rest) = strSplit opening haystack in
let (word, end) = strSplit closing rest in
(begining ++ opening, word, closing ++ end)
setLabelPN :: Lexicon -> String -> String
setLabelPN lexicon line =
let (_, word, _) = between ("\">", "</w>") line in
if word `member` lexicon
then
let (begining, _, ending) = between ("pos=\"", "\" ") line in
begining ++ "Np" ++ ending
else line
sed_i :: Lexicon -> FilePath -> IO ()
sed_i lexicon file = do
input <- lines <$> readFile file
writeFile destFile $ unlines (setLabelPN lexicon <$> input)
where
destFile = replaceDirectory file "CORPUS.fixed"
main :: IO ()
main = do
args <- getArgs
case args of
[lexiconFile] -> do
lexicon <- load lexiconFile
files <- lines <$> getContents
mapM_ (sed_i lexicon) files
_ -> die "Syntax: setPOS NP_LEXICON (filters files according to names read on stdin)"
```
Et encore 10 autres minutes pour écrire ces deux petites fonctions et c'était fini. J'ai repéré l'identifiant d'un fichier du corpus qui avait un nom propre mal annoté et ai lancé mon programme `setPos` sur une entrée standard ne contenant que le chemin de cet unique fichier pour tester. Il a fonctionné parfaitement du premier coup. Très satisfaisant.
## T+30 mn
À cet instant, j'ai commencé à y croire. Si tout s'exécutait aussi rapidement que je l'espérais, j'allais sans doute pouvoir rentrer chez moi pas si tard que ça. J'ai lancé le programme, en regardant régulièrement la taille du dossier grossir pour vérifier que tout allait bien. En quelques minutes, il avait atteint 16000 fichiers. J'ai commencé à ranger mes affaires, je suis allée laver ma tasse à café. Quand je suis revenue, une dizaine de minute après, tout était fini, les fichiers attendaient sagement l'import. En 40 mn, j'avais eu le temps de créer une solution bien plus rapide et de l'exécuter.
## Conclusion
Cet article n'a pas pour but d'essayer de faire croire que Haskell est le remède à tous les maux, qu'un langage compilé serait forcément plus rapide qu'un langage de script. Je suis persuadée qu'il était tout à fait possible d'écrire assez rapidement aussi un script équivalent en Perl ou en Python.
Le premier jet en Bash, lui, est trop désavantagé du manque de partage entre les différentes composantes, qui obligent à répliquer la lecture du lexique à chaque ligne de chaque fichier. Peut-être qu'il existait une solution élégante que j'ignore avec `sed` pour remplacer le code de la boucle interne qui itère sur les lignes en un seul `sed`. Mais même comme ça, je doute que les performances aient été très folichonnes, devant exécuter ce `sed` sur chaque fichier du corpus, rechargeant à chaque fois le lexique de 20 000 mots.
Un langage de script digne de ce nom aurait permis de créer un `hash` dans lequel il aurait été raisonablement rapide de vérifier l'existence d'une clef pour émuler cette structure de `Set` qui répond très vite sur l'appartenance d'un élément. J'aurais pu dans ces langages écrire une structure de boucle qui lise mes fichiers ligne à ligne, et j'aurais eu accès plus facilement à des expressions régulières pour transformer les lignes. Mais je suis moins à l'aise dans ces langages. Je sais écrire dedans, mais je n'ai pas la pratique nécessaire pour que toutes les primitives dont j'ai besoin viennent naturellement. J'aurais passé bien plus de temps à lire de la doc.
Ce que j'ai voulu montrer dans cet article, ce n'est pas que Haskell est spécialement fait pour ce genre de besoin. C'est que c'est un langage tout à fait utile aussi pour ce type de tâches et qu'il permet de produire rapidement un code relativement clair, sûr grâce à la vérification de type (combien de minutes j'aurais passé à me demander en Perl pourquoi il ne trouvait pas mon élément dans mon prototype de test, à ne pas savoir si je déréférençais bien le tableau ou si je testais quelque chose qui n'avait rien à voir ?) et assez rapide à l'exécution.
<br/>
------
PS: pour rigoler, j'ai quand même lancé le script Bash proposé en guise d'illustration de la solution lente sur le volume 7 seulement (3386 articles), pour me donner une idée du temps que ça aurait pris sur l'ensemble de l'Encyclopédie. Je n'ai pas eu le temps de le laisser finir mais en une vingtaine de minutes tout à l'heure il m'avait traité moins de 50 articles. En étant donc très très optimiste, on était donc plutôt parti sur `1400 * 20 mn = 28 000 mn ≃ 466.67 h > 19 j`. Ça valait le coup d'investir dans l'écriture de ce petit «script».
[^POS]: l'étiquette morpho-syntaxique pour celles et ceux qui n'auraient pas suivi le lien, habilement glissé dans le premier paragraphe, vers un autre article de ce blog qui rappelle un peu toutes ces notions de linguistique